package 回溯;

public class LeetCode733_图像渲染 {
    public int[][] nextP = {{1,0},{-1,0},{0,1},{0,-1}};
    public void DFS(int[][] image,int row,int col,int[][] book, int curX,int curY,
                    int oldColor, int newColor) {
        // 当前位置修改颜色
        image[curX][curY] = newColor;
        book[curX][curY] = 1;
        // 搜索上下左右
        for(int i = 0; i < 4; i++) {
            int newX = curX + nextP[i][0];
            int newY = curY + nextP[i][1];

            // 判断当前位置是否越界
            if(newX >= row || newX < 0 || newY >= col || newY < 0) {
                continue;
            }
            // 判断当前位置是否需要渲染
            if(image[newX][newY] == oldColor && book[newX][newY] == 0) {
                DFS(image, row, col, book, newX, newY, oldColor, newColor);
            }
        }
        return;
    }
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int row = image.length;
        int col = image[0].length;
        int[][] book = new int[row][col];
        int oldColor = image[sr][sc];
        DFS(image, row, col, book, sr, sc, oldColor, newColor);
        return image;
    }
}
